SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Day–Stout–Warren algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Day–Stout–Warren algorithm</span></span>

</h1>

</header>

<p>The <b>Day–Stout–Warren (DSW) algorithm</b> is a method for efficiently balancing <a href="Binary_search_tree" title="Binary search tree">binary search trees</a> – that is, decreasing their height to <a href="Big-O_notation" class="mw-redirect" title="Big-O notation">O</a>(log <i>n</i>) nodes, where <i>n</i> is the total number of nodes. Unlike a <a href="Self-balancing_binary_search_tree" title="Self-balancing binary search tree">self-balancing binary search tree</a>, it does not do this incrementally during each operation, but periodically, so that its cost can be <a href="Amortized_analysis" title="Amortized analysis">amortized</a> over many operations. The algorithm was designed by Quentin F. Stout and Bette Warren in a 1986 <a href="Communications_of_the_ACM" title="Communications of the ACM"><i>CACM</i></a> paper,<sup id="cite_ref-sw_1-0" class="reference"><a href="#cite_note-sw-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> based on work done by Colin Day in 1976.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>The algorithm requires linear (O(<i>n</i>)) time and is <a href="In-place_algorithm" title="In-place algorithm">in-place</a>. The original algorithm by Day generates as compact a tree as possible: all levels of the tree are completely full except possibly the bottom-most. It operates in two phases. First, the tree is turned into a <a href="Linked_list" title="Linked list">linked list</a> by means of an <a href="In-order_traversal" class="mw-redirect" title="In-order traversal">in-order traversal</a>, reusing the pointers in the (<a href="Threaded_binary_tree" title="Threaded binary tree">threaded</a>) tree's nodes. A series of <a href="Tree_rotation" title="Tree rotation">left-rotations</a> forms the second phase.<sup id="cite_ref-rolfe_3-0" class="reference"><a href="#cite_note-rolfe-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

The Stout–Warren modification generates a complete binary tree, namely one in which the bottom-most level is filled strictly from left to right. This is a useful transformation to perform if it is known that no more inserts will be done. It does not require the tree to be threaded, nor does it require more than <a href="Space_complexity" title="Space complexity">constant space</a> to operate.<sup id="cite_ref-sw_1-1" class="reference"><a href="#cite_note-sw-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Like the original algorithm, Day–Stout–Warren operates in two phases, the first entirely new, the second a modification of Day's rotation phase.<sup id="cite_ref-sw_1-2" class="reference"><a href="#cite_note-sw-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-rolfe_3-1" class="reference"><a href="#cite_note-rolfe-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p><p>A 2002 article by Timothy J. Rolfe brought attention back to the DSW algorithm;<sup id="cite_ref-rolfe_3-2" class="reference"><a href="#cite_note-rolfe-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> the naming is from the section title "6.7.1: The DSW Algorithm" in Adam Drozdek's textbook.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Rolfe cites two main advantages: "in circumstances in which one generates an entire binary search tree at the beginning of processing, followed by item look-up access for the rest of processing" and "pedagogically within a course on data structures where one progresses from the binary search tree into self-adjusting trees, since it gives a first exposure to doing rotations within a binary search tree."

</p>

<div class="mw-heading mw-heading2"><h2 id="Pseudocode">Pseudocode</h2></div>

<p>The following is a presentation of the basic DSW algorithm in <a href="Pseudocode" title="Pseudocode">pseudocode</a>, after the Stout–Warren paper.<sup id="cite_ref-sw_1-3" class="reference"><a href="#cite_note-sw-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>note 1<span class="cite-bracket">]</span></a></sup> It consists of a main routine with three <a href="Subroutine" class="mw-redirect" title="Subroutine">subroutines</a>. The main routine is given by

</p>

<ol><li>Allocate a node, the "pseudo-root", and make the tree's actual root the right child of the pseudo-root.</li>

<li>Call <i>tree-to-vine</i> with the pseudo-root as its argument.</li>

<li>Call <i>vine-to-tree</i> on the pseudo-root and the size (number of elements) of the tree.</li>

<li>Make the tree's actual root equal to the pseudo-root's right child.</li>

<li>Dispose of the pseudo-root.</li></ol>

<p>The subroutines are defined as follows:<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>note 2<span class="cite-bracket">]</span></a></sup>

</p>

<pre><b>routine</b> tree-to-vine(root)

// Convert tree to a "vine", i.e., a sorted linked list,

// using the right pointers to point to the next node in the list

tail ← root

rest ← tail.right

<b>while</b> rest ≠ nil

<b>if</b> rest.left = nil

tail ← rest

rest ← rest.right

temp ← rest.left

rest.left ← temp.right

temp.right ← rest

rest ← temp

tail.right ← temp

</pre>

<pre><b>routine</b> vine-to-tree(root, size)

leaves ← size + 1 − 2<sup>⌊log<sub>2</sub>(size + 1)⌋</sup>

compress(root, leaves)

size ← size − leaves

<b>while</b> size > 1

compress(root, ⌊size / 2⌋)

size ← ⌊size / 2⌋

</pre>

<pre><b>routine</b> compress(root, count)

scanner ← root

<b>for</b> i ← 1 <b>to</b> count

child ← scanner.right

scanner.right ← child.right

scanner ← scanner.right

child.right ← scanner.left

scanner.left ← child

</pre>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">This version does not produce perfectly balanced nodes; Stout and Warren present a modification that does, in which the first call to <style data-mw-deduplicate="TemplateStyles:r886049734">

/* start https://en.wikipedia.org/ */

.mw-parser-output .monospaced{font-family:monospace,monospace}

/* end https://en.wikipedia.org/ */

</style><span class="monospaced">compress</span> is replaced by a different subroutine.</span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text">In the original presentation, <i>tree-to-vine</i> computed the tree's size as it went. For the sake of brevity, we assume this number to be known in advance.</span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFStoutWarren1986" class="citation journal cs1">Stout, Quentin F.; Warren, Bette L. (September 1986). <a rel="nofollow" class="external text" href="http://www.eecs.umich.edu/~qstout/pap/CACM86.pdf">"Tree rebalancing in optimal space and time"</a> <span class="cs1-format">(PDF)</span>. <i>Communications of the ACM</i>. <b>29</b> (9): <span class="nowrap">902–</span>908. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F6592.6599">10.1145/6592.6599</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/2027.42%2F7801">2027.42/7801</a></span>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:18599490">18599490</a>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFDay1976" class="citation journal cs1">Day, A. Colin (1976). <a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fcomjnl%2F19.4.360">"Balancing a Binary Tree"</a>. <i><a href="The_Computer_Journal" title="The Computer Journal">Comput. J.</a></i> <b>19</b> (4): <span class="nowrap">360–</span>361. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fcomjnl%2F19.4.360">10.1093/comjnl/19.4.360</a></span>.</cite></span>

</li>

<li id="cite_note-rolfe-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-rolfe_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-rolfe_3-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-rolfe_3-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFRolfe2002" class="citation journal cs1">Rolfe, Timothy J. (December 2002). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="http://penguin.ewu.edu/~trolfe/DSWpaper/">"One-Time Binary Search Tree Balancing: The Day/Stout/Warren (DSW) Algorithm"</a></span>. <i>SIGCSE Bulletin</i>. <b>34</b> (4). ACM SIGCSE: <span class="nowrap">85–</span>88. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F820127.820173">10.1145/820127.820173</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14051647">14051647</a>. <a rel="nofollow" class="external text" href="https://archive.today/20121213000401/http://penguin.ewu.edu/~trolfe/DSWpaper/">Archived</a> from the original on 2012-12-13.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFDrozdek1996" class="citation book cs1">Drozdek, Adam (1996). <i>Data Structures and Algorithms in C++</i>. PWS Publishing Co. pp. <span class="nowrap">173–</span>175. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-534-94974-6</bdi>.</cite></span>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-24" href="https://en.wikipedia.org/wiki/?title=Day%E2%80%93Stout%E2%80%93Warren_algorithm&oldid=1291979988">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>